//链接：https://leetcode.cn/problems/implement-trie-prefix-tree/description/
//使用vector实现：
struct Node
{
    int pass = 0;
    int end = 0;
    vector<Node*> nexts;
    Node()
    {
        nexts.resize(26,nullptr);
        pass = end = 0;
    }
};
class Trie {
public:
    Trie() {
        root = new Node();
    }
    
    void insert(string word) {
        if(word == "") return ;
        int n = word.size();
        Node* cur = root;
        cur->pass++;
        for(int i = 0;i<n;i++)
        {
            int path = word[i] - 'a';
            if(cur->nexts[path] == nullptr)
                cur->nexts[path] = new Node();
            cur = cur->nexts[path];
            cur->pass++;
        }
        cur->end++;
    }
    
    bool search(string word) {
        if(word == "") return false;
        int n = word.size();
        Node* cur = root;
        for(int i = 0;i<n;i++)
        {
            int path = word[i] - 'a';
            if(cur->nexts[path] == nullptr) return false;
            cur = cur->nexts[path];
        }
        return cur->end > 0;
    }
    
    bool startsWith(string prefix) {
        int n = prefix.size();
        Node* cur = root;
        for(int i = 0;i<n;i++)
        {
            int path = prefix[i] - 'a';
            if(cur->nexts[path] == nullptr) return false;
            cur = cur->nexts[path];
        }
        return cur->pass > 0;
    }
private:
    Node* root;
};

//使用map/unordered_map实现
struct Node
{
    int pass = 0;
    int end = 0;
    unordered_map<char,Node*> nexts;
};
class Trie {
public:
    Trie() {
        root = new Node();
    }
    
    void insert(string word) {
        if(word == "") return ;
        int n = word.size();
        Node* cur = root;
        cur->pass++;
        for(int i = 0;i<n;i++)
        {
            char path = word[i];
            if(cur->nexts[path] == nullptr)
                cur->nexts[path] = new Node();
            cur = cur->nexts[path];
            cur->pass++;
        }
        cur->end++;
    }
    
    bool search(string word) {
        if(word == "") return false;
        int n = word.size();
        Node* cur = root;
        for(int i = 0;i<n;i++)
        {
            char path = word[i];
            if(cur->nexts[path] == nullptr) return false;
            cur = cur->nexts[path];
        }
        return cur->end > 0;
    }
    
    bool startsWith(string prefix) {
        int n = prefix.size();
        Node* cur = root;
        for(int i = 0;i<n;i++)
        {
            char path = prefix[i];
            if(cur->nexts[path] == nullptr) return false;
            cur = cur->nexts[path];
        }
        return cur->pass > 0;
    }
private:
    Node* root;
};
